\section{Desarrollo}

A continuación detallamos cómo fue el desarrollo de los algoritmos presentados previamente

\subsection{Page Rank}
El desarrollo del algoritmo de PageRank lo dividimos en dos etapas, inicializaci\'on  y calculo de PageRank. Este mismo se basa en el algoritmo original de PageRank mencionado en la sección, con la salvedad de que realizamos optimizaciones que mencionaremos más adelante.\\
\\
En la primera etapa de Inicialización se reciben 3 parametros, el valor de c, la cantidad de sitios y un vector con los links que apuntan cada sitio. Primero generamos un vector inicial arbitrario, en nuestro caso elegimos el que recomendaban Bryan y Leise $[3]$ que tiene el primer elemento en 1 y los demás en 0. Luego generamos $M_f$ representandolo con un DOK ya que la matriz resultante en la mayoría de los casos es una matriz dispersa y definiendola con los valores como indica el algoritmo, quedando como resultado una matriz estocástica. Además, como los necesitaremos más adelante y para ahorrar tiempos de cómputo, guardamos los sitios que no apuntan a nadie en un vector de \textit{desconectados}.

Inicializaci\'on:
\begin{algorithm}
\caption{inicializar(c, dim, links)}\label{euclid}
\begin{algorithmic}[1]
\State $\textit{$v_{inicial}$ = vector(dim, 0);}$ \Comment{creo un vector de dim elementos y lo inicializo en 0}
\State $\textit{$v_{inicial}$[0] = 1;}$ \Comment{pongo el primer elemento en 1}
\State $\textit{$M_f$ = DOK(dim);}$ \Comment{la matriz en forma de DictionaryOfKeys representará al $M_f$}
\State $\textit{desconectados = vector()}$ \Comment{creo un vector para almacenar los nodos que no tienen salidas}
\For{$cada\ link\ en\ links$}
	\If{$link\ tiene\ salidas$}
		\State $\textit{n = link.cantidadDeSalidas;}$
		\For{$cada\ salida\ del\ nodo$}
			\State $\textit{$M_f$.definir(salida, link, 1/n );}$ \Comment{A cada salida del link actual le doy puntaje de 1/n}
		\EndFor
		\Else
			\State $\textit{desconectados.agregar(link);}$ 
	\EndIf
\EndFor
\end{algorithmic}
\end{algorithm}

En la segunda etapa del cálculo del PageRank se resuelve mediante el método de las potencias, para esto se utiliza el vector generado en la etapa anterior y se multiplica sucesivamente por la matriz hasta que norma Manhattan entre los vectores de las diferentes iteraciones alcanzan un valor de convergencia. Como el algoritmo requiere sumar valores a todas las posiciones de la matriz para simular la noción de \textit{teletransportación} se pierde la ventaja de que la matriz sea dispersa y por consiguiente todas sus optimizaciones. Por tal motivo, para no perder esta caracteristica de la matriz lo que hacemos es operar con los resultados del vector donde le aplicamos los calculos necesarios sin la necesidad de modificar $M_f$.

Cálculo del PageRank:
\begin{algorithm}
\caption{calcular()}\label{euclid}
\begin{algorithmic}[1]
\State  $\textit{v = $v_{inicial}$}$
\While{$norma > tolerancia$} \Comment{hasta que converja}
	\State $\textit{w = v}$ \Comment{guardo el vector anterior para calcular la norma Manhattan más adelante}
	\State  $\textit{sumaDesconectados = 0}$
	\For{cada link desconectado: $linkDesconectado$}
		\State $\textit{sumaDesconectados += v.elemento(linkDesconectado)}$ \Comment{}
	\EndFor
	\State $\textit{v = $M_f$ v}$ \Comment{aplico una iteraci'n del método de la potencia}
	\For{cada elemento de v: $v_i$}
		\State $\textit{$v_i$ = c*($v_i$+sumaDesconectados)+((1-c)/links.tamaño)  ;}$ \Comment{}
	\EndFor
	\State $\textit{norma = manhattan(v,w)}$ \Comment{calculo la norma Manhattan}
\EndWhile
\end{algorithmic}
\end{algorithm}
 
\newpage
\subsection{HITS}
Este también lo dividimos en la etapa en la etapa de inicialización y de cálculo de sus vectores. En la primera creamos la matriz estocástica e inicializamos los vectores y en la segunda calculamos los mismos hasta que iteremos k veces o la diferencia obtenida sea menor que la tolerancia.

\begin{algorithm}
\caption{inicializar(grafo)}\label{euclid}
\begin{algorithmic}[1]
\State  $\textit{dok = nuevoDOK()}$
\For{cada nodo del grafo}
	\State $\textit{nodosLlegada = nodo.obtenerNodosALosQueLlega();}$	
	\For{nodo2 de nodosLlegada}		
		\State $\textit{dok.definir(nodo1,nodo2,1)}$ 
	\EndFor	
\EndFor
\State  $\textit{vectorHubs = nuevoVectorConUnos(grafo.cantNodos())}$
\State  $\textit{vectorAutoridades = nuevoVectorConUnos(grafo.cantNodos())}$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{calculoAutoridadesYHubs(tolerancia)}\label{euclid}
\begin{algorithmic}[1]
	\State $\textit{dokTranspuesto = dok.transponer();}$
\For{1 a K}
	\State $\textit{vectorHubsPrevio = vectorHubs;}$
	\State $\textit{vectorAutoridadesPrevio = vectorAutoridades;}$
	\State $\textit{vectorHubs = dokTranspuesto X vectorHubs;}$
	\State $\textit{vectorHubs.normalizar();}$
	\State $\textit{vectorAutoridades = dok X vectorAutoridades;}$
	\State $\textit{vectorAutoridades.normalizar();}$
	\State $\textit{toleranciaAutoridades = NormaManhattan(vectorAutoridades,vectorAutoridadesPrevio);}$
	\State $\textit{toleranciaHubs = NormaManhattan(vectorHubs,vectorHubsPrevio);}$
	\If{$toleranciaHubs < tolerancia || toleranciaAutoridades < tolerancia$}
		\State $\textit{break;}$
	\EndIf
\EndFor
\end{algorithmic}
\end{algorithm}

\subsection{Indeg}

La implementación de este algoritmo es bastante simple. Tomamos un vector inicial con ceros del tamaño de las páginas y recorremos todas las referencias de cada página hacia al resto, y por cada una de los sitios a los que visita, le sumamos en 1/cantidadLinksTotal su puntaje en el vector inicial.

\begin{algorithm}
\caption{calcular(links)}\label{euclid}
\begin{algorithmic}[1]
\State $\textit{$v_{inicial}$ = vector(links.size, 0);}$ \Comment{creo un vector de dim elementos y lo inicializo en 0}
\State $\textit{$totalAmountOfDomains$ = links.size;}$ 
\For{$cada\ link\ en\ links$}
	\If{$link\ tiene\ salidas$}
		\For{$cada\ salida\ del\ nodo$}
			\State $\textit{$v[salida] = v[salida] + 1/totalAmountOfDomains;$}$ \Comment{A cada salida del link actual le sumo el puntaje 1/totalAmountOfDomains}
		\EndFor
	\EndIf
\EndFor
\end{algorithmic}
\end{algorithm}
